package com.jack.leetcode.editor.cn;
//给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。
//
// 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。 
//
// 你可以按任意顺序返回答案。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [2,7,11,15], target = 9
//输出：[0,1]
//解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
// 
//
// 示例 2： 
//
// 
//输入：nums = [3,2,4], target = 6
//输出：[1,2]
// 
//
// 示例 3： 
//
// 
//输入：nums = [3,3], target = 6
//输出：[0,1]
// 
//
// 
//
// 提示： 
//
// 
// 2 <= nums.length <= 103 
// -109 <= nums[i] <= 109 
// -109 <= target <= 109 
// 只会存在一个有效答案 
// 
// Related Topics 数组 哈希表 
// 👍 10859 👎 0


import java.util.HashMap;
import java.util.Map;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution02 {

    public static void main(String[] args) {
        Solution02 solution02 = new Solution02();
        int[] ints = solution02.twoSum(new int[]{3,2,4}, 6);
        for (int anInt : ints) {
            System.out.println(anInt);
        }
    }

//      暴力循环解
//    public int[] twoSum(int[] nums, int target) {
//        if ( nums == null ||nums.length == 0 ){
//            return null;
//        }
//
////      设置1个指针，指向数组第一位。 做一个双重循环 。 当条件符合时（数字a 与数字b的和为目标数字时），循环结束。
//
//        for (int i = 0; i < nums.length; i++) {
//            for (int j = 0; j < nums.length; j++) {
//                if (nums[i] + nums[j] == target && i != j){
//                     return new int[]{i , j};
//                }
//            }
//        }
//        return null;
//    }


    /**
     * todo 暴力循环获取值内存优化。 减少不必要的循环次数。
     * @param nums
     * @param target
     * @return
     */
//   public int[] twoSum(int[] nums, int target) {
//       if (nums == null || nums.length == 0) {
//           return null;
//       }
//
//       for (int i = 0; i < nums.length; i++) {
//           for (int j = i+1 ; j <nums.length ; j++) {
//               if (nums[i] + nums[j] == target){
//                   return new int[]{i, j};
//               }
//           }
//       }
//       return null;
//   }

    /**
     * todo 哈希表
     *
     * hashMap是由数组与链表组成， 数组是主题，链表用于处理哈希冲突
     * 一个hashMap的链表数量越少，性能越好
     *
     * todo hashTable表中key 用来存放数组中的数值。 value 用来存放数组中元素的下标。
     * todo 不需要再增加指针用来标识元素下标。 只需要一次循环可以得到所需的值
     */


    public int[] twoSum(int[]nums , int target){
        Map<Integer,Integer> hashTable = new HashMap<Integer , Integer>();
        for (int i = 0; i < nums.length; ++i) {
            if (hashTable.containsKey(target - nums[i])){
                return new int[]{hashTable.get(target - nums[i]) , i};
            }
            hashTable.put(nums[i] , i);
        }
        return null;
    }

}
//leetcode submit region end(Prohibit modification and deletion)
